package com.engine.cn.leetcode.array;

/**
 * 二分查找原理非常简答， 但是细节很多，并不容易，个人感觉要难于链表
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
 * 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 * 这里以左闭右开区间为例，处理边界问题 [left,right)
 */
public class BinarySearch {

    public static int search(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int left = 0;
        int right = arr.length;

        //由于是左闭右开，所以不能等于
        while (left < right) {
            int middle = (left + right) >>> 1;
            if (arr[middle] > target) {
                right = middle;
            } else if (arr[middle] < target) {
                //这里左闭右开
                left = middle + 1;
            } else {
                return middle;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {-1, 0, 3, 5, 9, 12};
        int result = search(arr, 9);
        System.out.println("result==>" + result);
    }
}
